package main

import (
	"fmt"
)

func match(str, pattern string) bool {
	return matchCore(str, pattern, 0, 0)
}

func matchCore(str, pattern string, strLoc, patLoc int) bool {
	if patLoc == len(pattern) && strLoc == len(str) {
		return true
	}
	if patLoc == len(pattern) && strLoc != len(str) {
		return false
	}

	if patLoc+1 < len(pattern) && pattern[patLoc+1] == '*' {
		if strLoc < len(str) && str[strLoc] == pattern[patLoc] {
			return matchCore(str, pattern, strLoc, patLoc+2) ||
				matchCore(str, pattern, strLoc+1, patLoc+2) ||
				matchCore(str, pattern, strLoc+1, patLoc)
		}
		return matchCore(str, pattern, strLoc, patLoc+2)
	}

	if strLoc < len(str) && pattern[patLoc] == str[strLoc] {
		return matchCore(str, pattern, strLoc+1, patLoc+1)
	}
	return false
}

func main() {
	var str1, str2 = "abc", "a*bc"
	var str3 = "aa*"
	fmt.Println(match(str1, str2))
	fmt.Println(match(str1, str3))
}
